import heuristic as ModHeristic
from heapq import *

BOX_MOVE_WEIGHT = 1

class HeuristicHelper(object):
    '''
    Base Class
    '''
    BOX_HEURISTIC_MODE = dict(zip(['DYNAMIC', 'GREEDY'], range(2)))
    
    def __init__(self, sokoban_heuristic, state):
        '''
        Constructor
        '''
        self.smap = sokoban_heuristic.smap
        self.state = state
        self.boxes_amount = len(state.objects)
        self._boxes_distances = []
        self._current_min_value = ModHeristic.BIG
        self._box_heuristic_mode = HeuristicHelper.BOX_HEURISTIC_MODE['DYNAMIC']
        
        self.get_box_distances()
        
    
    def h(self):
        ''' h = h_box + h_player
        '''
        if self._box_heuristic_mode == HeuristicHelper.BOX_HEURISTIC_MODE['DYNAMIC']:            
            h_box = self.get_h_box_dynamic()
        elif self._box_heuristic_mode == HeuristicHelper.BOX_HEURISTIC_MODE['GREEDY']:
            h_box = self.get_h_box_greedy();
        else:
            h_box = 0
        
        h_player = self.get_player_nearest_distance()
        
        return h_box * BOX_MOVE_WEIGHT + h_player
    
    def get_h_box_dynamic(self):
        h_box, best_schema = self.get_h_box_dynamic_recursion(0, 0,                                                      
            #all destinations are all available
            range(self.boxes_amount),
            #all i box 's destination is not yet decided (-1) 
            [-1 for i in range(self.boxes_amount)])
        return h_box
        
    def get_h_box_dynamic_recursion(self, current_value, i_box, avail_dest, schema):
        min_recurrsive_value = ModHeristic.BIG
        best_dest = -1
        best_schema = []
        best_schema.extend(schema)
        
        #i_dest: the index of a destination coord
        for i_dest in avail_dest:
            
            # if i_box can not reach that i_dest, then don't give a try
            if self._boxes_distances[i_box][i_dest] == -1 :
                continue
                        
            #So if this expansion has already exceed the minimum lowest value for full schema
            #Then it would be ridiculous to go any further     
            temp_value = current_value + self._boxes_distances[i_box][i_dest]
            if(temp_value > self._current_min_value):
                continue
            
            #recursion
            tmp_schema = []
            tmp_schema.extend(schema)
            tmp_schema[i_box] = i_dest
            if(len(avail_dest) == 1):
                temp_recursion_value = 0
            else:
                temp_avail_dest = []
                temp_avail_dest.extend(avail_dest)
                temp_avail_dest.remove(i_dest)
                temp_recursion_value, tmp_schema = self.get_h_box_dynamic_recursion(
                            temp_value, i_box + 1, temp_avail_dest, tmp_schema)
            
            temp_recursion_value += self._boxes_distances[i_box][i_dest]
            
            #update the minimum recursion value can get by now
            if(temp_recursion_value < min_recurrsive_value):
                min_recurrsive_value = temp_recursion_value
                best_schema = []
                best_schema.extend(tmp_schema)
                best_dest = i_dest
        
        #when the last permutation element        
        if(len(avail_dest) == 1 and self._boxes_distances[i_box][best_dest] != -1):
            temp_value = current_value + self._boxes_distances[i_box][best_dest]
            if(temp_value < self._current_min_value):
                self._current_min_value = temp_value
                
            
        return (min_recurrsive_value, best_schema)
    
    def get_h_box_greedy(self):
        summation = 0
        
        for elem in self._boxes_distances:
            summation += heappop(elem)
        
        return summation
        
class ManhattanHelper(HeuristicHelper):
    
    def __init__(self, sokoban_heuristic, state):
        HeuristicHelper.__init__(self, sokoban_heuristic, state)

    def get_box_distances(self):
        boxes_distances = [[0] * self.boxes_amount for i in range(self.boxes_amount)];
        
        for i, box in enumerate(self.state.objects):            
            for j, goal in enumerate(self.smap.goals):
                boxes_distances[i][j] = ModHeristic.manhattan_distance(box, goal)
        
        self._boxes_distances = boxes_distances        
        return boxes_distances
    
    def get_player_nearest_distance(self):
        distances = []
        for key in self.state.objects:
            heappush(distances, ModHeristic.manhattan_distance(self.state.playerCoord, key))
            
        return heappop(distances);
    
class NavigationHelper(HeuristicHelper):
    
    def __init__(self, sokoban_heuristic, state):
        HeuristicHelper.__init__(self, sokoban_heuristic, state)

    def get_box_distances(self):
        boxes_distances = [[0] * self.boxes_amount for i in range(self.boxes_amount)];
        
        for i, box in enumerate(self.state.objects): 
            value_map = ModHeristic.block_navigation_search(box, self.smap)           
            for j, goal in enumerate(self.smap.goals):
                boxes_distances[i][j] = value_map[0][goal[1] * self.smap.w + goal[0]]
        
        self._boxes_distances = boxes_distances        
        return boxes_distances
    
    def get_player_nearest_distance(self):
        distances = []
        player_value_map = ModHeristic.navigation_search(
                        self.state.playerCoord, self.smap)[0]
        
        for key in self.state.objects:
            heappush(distances, player_value_map[key[1] * self.smap.w + key[0]])
            
        return heappop(distances)

class CachedNavigationHelper(NavigationHelper):
    cache_box_distances = {}
    cache_player_box = {} # two-level dictionary,first box status, then player
    cache_box_allocations = {}
    
    # for debugging
    __hit_box_distances = 0
    __hit_player_box = 0
    __hit_box_allocations = 0
    
    def __init__(self, sokoban_heuristic, state):
        NavigationHelper.__init__(self, sokoban_heuristic, state)

    def get_box_distances(self):
        #look up cache first
        key = frozenset(self.state.objects)
        value = CachedNavigationHelper.cache_box_distances.get(key)
        
        if value == None:
            value = super(CachedNavigationHelper, self).get_box_distances()
            CachedNavigationHelper.cache_box_distances.update({key:value})
        else:
            CachedNavigationHelper.__hit_box_distances+=1
        
        self._boxes_distances = value
        return value
    
    def get_player_nearest_distance(self):
        #two level search
        #first look up box status
        key_1 = frozenset(self.state.objects)
        value_1 = CachedNavigationHelper.cache_player_box.get(key_1)
        
        key_2 = self.state.playerCoord
        update_first_level = False
        
        if value_1 != None:
            value_2 = value_1.get(key_2)
        else:
            value_1 = {}            
            value_2 = None
            update_first_level = True
        
        if(value_2 == None):
            value_2 = super(CachedNavigationHelper, self).get_player_nearest_distance()
            value_1.update({key_2 : value_2})
            update_first_level = True
        else:
            CachedNavigationHelper.__hit_player_box+=1
        
        if update_first_level:
            CachedNavigationHelper.cache_player_box.update({key_1 : value_1})
        
            
        return value_2
    
    def get_h_box_dynamic(self):
        key = frozenset(self.state.objects)
        value = CachedNavigationHelper.cache_box_allocations.get(key)
        
        if value == None:
            value = super(CachedNavigationHelper, self).get_h_box_dynamic()
            CachedNavigationHelper.cache_box_allocations.update({key:value})
        else:
            CachedNavigationHelper.__hit_box_allocations+=1
            
        return value
